{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# THE DEUTSCH-JOZSA ALGORITHM\n",
    "\n",
    "We are going to use Qiskit to implement the Deutsch-Jozsa algorithm "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "\n",
    "from qiskit import *\n",
    "from qiskit.visualization import *\n",
    "from qiskit.tools.monitor import *\n",
    "\n",
    "n = 4 # Number of qubits that we are going to use in the oracle\n",
    "\n",
    "q   = QuantumRegister(n, 'q') # The oracle qubits\n",
    "out = QuantumRegister(1, 'out') # Qubit for the oracle output\n",
    "c   = ClassicalRegister(n, 'c') # Classical bits needed for the result of the measurement\n",
    "\n",
    "circ_init = QuantumCircuit(q,out,c) # Initial part of the circuit\n",
    "\n",
    "for i in range(n):    \n",
    "    circ_init.h(q[i]) # We apply H to all the oracle qubits\n",
    "    \n",
    "circ_init.x(out)  # We apply X and H to the output qubit\n",
    "circ_init.h(out)\n",
    "\n",
    "circ_init.barrier() # Visual barrier to separate the parts of the circuit\n",
    "\n",
    "circ_init.draw(output='mpl')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "circ_end = QuantumCircuit(q,out,c)\n",
    "\n",
    "circ_end.barrier() # Visual barrier to separate the parts of the circuit\n",
    "\n",
    "for i in range(n):    \n",
    "    circ_end.h(q[i]) # We apply H to all the oracle qubits\n",
    "    \n",
    "circ_end.measure(q,c)\n",
    "\n",
    "circ_end.draw(output='mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, we are going to define two oracles to check the behaviour of the algorithm. One will be a circuit for a constant function and the other, for a balanced function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Oracle for a boolean function that always returns 1 \n",
    "    \n",
    "const = QuantumCircuit(q,out,c)\n",
    "const.cx(q[0],out)\n",
    "const.x(q[0])\n",
    "const.cx(q[0],out)\n",
    "const.x(q[0])\n",
    "\n",
    "const.draw(output='mpl')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Oracle for a boolean function that returns 1 for half of the inputs\n",
    "    \n",
    "bal = QuantumCircuit(q,out,c)\n",
    "bal.cx(q[0],out)\n",
    "\n",
    "bal.draw(output='mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We create the circuit with the oracle for the constant function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "circ_const = circ_init + const + circ_end\n",
    "circ_const.draw(output='mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When we execute it, the result of the measure is, as expected, a string formed only by zeroes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "backend = Aer.get_backend('qasm_simulator')\n",
    "job = execute(circ_const, backend, shots=10)\n",
    "counts = job.result().get_counts()\n",
    "print(counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we build the circuit for the balanced function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "circ_bal = circ_init + bal + circ_end\n",
    "circ_bal.draw(output='mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When we run it, we always obtain a string that is not all zeroes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "job = execute(circ_bal, backend, shots=10)\n",
    "counts = job.result().get_counts()\n",
    "print(counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are now going to execute the circuit on a quantum computer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit.providers.ibmq import least_busy\n",
    "\n",
    "provider = IBMQ.load_account()\n",
    "# We choose the least busy device\n",
    "backend = least_busy(provider.backends(operational = True, simulator=False, status_msg='active',\n",
    "                                       filters=lambda x: x.configuration().n_qubits >= n+1)) \n",
    "print(\"We are using...\",backend)\n",
    "print(\"It has\",backend.status().pending_jobs,\"pending jobs\")\n",
    "# We send both circuits at a time\n",
    "circuits = [circ_const,circ_bal]\n",
    "job_exp = execute(circuits, backend=backend)\n",
    "job_monitor(job_exp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once the job is done, we obtain and show the results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "result_exp = job_exp.result()\n",
    "counts_const = result_exp.get_counts(circ_const)\n",
    "print(\"Results for the circuit with the constant function\")\n",
    "print(counts_const)\n",
    "print()\n",
    "counts_equi = result_exp.get_counts(circ_bal)\n",
    "print(\"Results for the circuit with the balanced function\")\n",
    "print(counts_equi)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
